package com.lin;


public class Solution {
    static int[] x = {1,-1,0,0};
    static int[] y = {0,0,1,-1};
    static float [][]f ;

    public int countk(int m, int n, int k){
        int ans = 0;
        while(m>0){
            ans += m%10;
            m /= 10;
        }
        while(n>0){
            ans += n%10;
            n /= 10;
        }
        if(ans > k)
            return 0;
        else
            return 1;
    }

    public void dfs(int i, int j, int m, int n, int k){
        if(i<0 || i>m-1) return;
        if(j<0 || j>n-1) return;
        if(countk(i,j,k)==0) return;
        if(f[i][j]==1) return;
        for (int l = 0; l < 4; l++) {
            f[i][j] = 1;
            dfs(i+x[l],j+y[l],m,n,k);
        }
    }


    public int movingCount(int m, int n, int k) {
        f = new float[m][n];
        dfs(0,0,m,n,k);
        int result = 0;
        for(int i = 0;i<m;i++){
            for(int j=0;j<n;j++){
                result += f[i][j];
            }
        }
        return result;
    }
}